package com.leetcode.number;

/**
 * 最长回文字符串
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba"也是一个有效答案。
 */
public class LongestPalindrome {

    int low = 0, maxLen = 0;

    public String longestPalindrome(String s) {

        int len = s.length();
        if (len < 2) {
            return s;
        }
        for (int i = 0; i < len - 1; i++) {
            calSplitIndex(s, i, i);
            calSplitIndex(s, i, i + 1);
        }
        return s.substring(low, low + maxLen);
    }

    /**
     * 计算位置
     */
    private void calSplitIndex(String s, int m, int n) {
        while (m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
            m--;
            n++;
        }
        if (maxLen < n - m - 1){
            low = m+1;
            maxLen= n-m-1;
        }
    }

    public static void main(String[] args) {
        String str = "babad";
        System.out.println(new LongestPalindrome().longestPalindrome(str));
    }
}
